package com.yun.algorithmproblem.leetcode;

import java.util.ArrayList;
import java.util.Arrays;

public class Leetcode2438 {

    private static final int MOD = 1000000007;

    public static void main(String[] args) {
        Leetcode2438 obj = new Leetcode2438();
        int n = 15;
        int[][] queries = new int[][]{{0, 1}, {2, 2}, {0, 3}};
        int[] ans = obj.productQueries(n, queries);
        System.out.println(Arrays.toString(ans));
    }

    public int[] productQueries(int n, int[][] queries) {
        ArrayList<Integer> list = new ArrayList<>();
        int bits = 0;
        int sum = 0;
        while (n > 0) {
            if ((n & 1) == 1) {
                sum += bits;
                list.add(sum);
            }
            n = n >> 1;
            bits++;
        }

        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int rangeSum = list.get(queries[i][1]) - (queries[i][0] - 1 < 0 ? 0 : list.get(queries[i][0] - 1));
            ans[i] = fastPow(2, rangeSum, MOD);
        }
        return ans;
    }

    private int fastPow(int base, int exponent, int mod) {
        long result = 1;
        long baseLong = base;
        while (exponent > 0) {
            if ((exponent & 1) == 1) {
                result = (result * baseLong) % mod;
            }
            baseLong = (baseLong * baseLong) % mod;
            exponent = exponent >> 1;
        }
        return (int) result;
    }
}
